package org.example.sort;

import java.util.Scanner;

public class HeapSort {
    //堆排序
    //思路 构建大顶堆 从最后一个的非叶子节点n/2-1开始下沉，调整
    //排序，最大的拿下来，交换，len-1 ，给heapify len，0 调整保持堆
    //调整堆方法 当前节点 左：i*2+1 右：i*2+2 左右有比他大的就换 下标 最后有动过，就交换，并再一次递归调整
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] nums=new int[n];
        for (int i = 0; i < nums.length; i++) {
            nums[i] =sc.nextInt();
        }
        heapsort(nums);
        for(int num:nums){
            System.out.println(num);
        }

    }

    private static void heapsort(int[] nums) {
        int n= nums.length;
        for (int i = n/2-1; i>=0; i--) {
            heapify(nums,n,i);
        }
        for(int i=n-1;i>0;i--){
            int t=nums[i];
            nums[i]=nums[0];
            nums[0]=t;
            heapify(nums,i,0);
        }
    }

    private static void heapify(int[] nums, int len, int i) {
        int l=i*2+1;
        int r=i*2+2;
        int largest=i;
        if(l<len&&nums[l]>nums[largest]){
            largest=l;
        }
        if(r<len&&nums[r]>nums[largest]){
            largest=r;
        }
        if(largest!=i){
            int t=nums[i];
            nums[i]=nums[largest];
            nums[largest]=t;
            heapify(nums,len,largest);
        }
    }



/*    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] nums = new int[n];
        for (int i = 0; i < nums.length; i++) {
            nums[i] = sc.nextInt();
        }
        heapsorts(nums);
        for(int num:nums){
            System.out.println(num);
        }
    }

    private static void heapsorts(int[] nums) {
        int n = nums.length;
        for (int i = n / 2 - 1; i >= 0; i--) {
            heapify(nums, n, i);
        }
        for (int i = n - 1; i > 0; i--) {
            int t=nums[0];
            nums[0]=nums[i];
            nums[i]=t;

            heapify(nums,i,0);
        }

    }

    private static void heapify(int[] nums, int len, int i) {
        int largest = i;
        int l = 2 * i + 1;
        int r = 2 * i + 2;
        if (l < len && nums[l] > nums[largest]) {
            largest = l;
        }
        if (r < len && nums[r] > nums[largest]) {
            largest = r;
        }
        if (largest != i) {
            int t = nums[i];
            nums[i] = nums[largest];
            nums[largest] = t;
            heapify(nums, len, largest);
        }
    }*/
}
